class Solution(object):
    def kConcatenationMaxSum(self, arr, k):
        max_val = 0
        now = 0
        for num in arr:
            now += num
            if now >= 0:
                max_val = max(max_val, now)
            else:
                now = 0
        if k == 1:
            return max_val
        pre_max = 0
        pre_now = 0
        suff_max = 0
        suff_now = 0
        n = len(arr)
        for i in range(n):
            pre_now += arr[i]
            suff_now += arr[n - 1 - i]
            pre_max = max(pre_max, pre_now)
            suff_max = max(suff_max, suff_now)
        t = sum(arr)
        max_val = max(max_val, pre_max + suff_max)
        if t > 0:
            max_val = max(max_val, pre_max + suff_max + (k - 2) * t)
        return max_val % (10 ** 9 + 7)


